package com.agile.leetcode.hot.middle;

import java.util.*;

/**
 * 49. 字母异位词分组
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * <p>
 * 示例:
 * <p>
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出:
 * [
 * ["ate","eat","tea"],
 * ["nat","tan"],
 * ["bat"]
 * ]
 *
 * @Author:ChenZhangKun
 * @Date: 2021/5/21 14:37
 */
public class GroupAnagrams {
    public static void main(String[] args) {
        GroupAnagrams anagrams = new GroupAnagrams();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = anagrams.groupAnagrams(strs);
        System.out.println(lists);
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        // 参数校验
        if (strs == null) {
            throw new NullPointerException("strs不能为null");
        }
        // 创建集合
        List<List<String>> out = new ArrayList<>(10);
        if (strs.length == 1) {
            List<String> in = new ArrayList<>(10);
            in.add(strs[0]);
            out.add(in);
            return out;
        }
        // 创建map
        Map<String, List<String>> map = new HashMap<>(16);
        // 遍历数组
        for (String str : strs) {
            // 转为字符集
            char[] chars = str.toCharArray();
            // 排序
            Arrays.sort(chars);
            // 转为串
            String sortStr = new String(chars);
            // 是否有key
            if (map.containsKey(sortStr)) {
                map.get(sortStr).add(str);
            } else {
                List<String> list = new ArrayList<>(10);
                list.add(str);
                map.put(sortStr, list);
            }
        }
        out.addAll(map.values());
        return out;
    }
}
